<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222"><meta name="generator" content="Hexo 6.3.0">

  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.2.1/css/all.min.css" integrity="sha256-Z1K5uhUaJXA7Ll0XrZ/0JhX4lAtZFpT6jkKrEDT0drU=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">

<script class="next-config" data-name="main" type="application/json">{"hostname":"example.com","root":"/","images":"/images","scheme":"Muse","darkmode":false,"version":"8.14.1","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":{"enable":false,"style":null},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"stickytabs":false,"motion":{"enable":true,"async":false,"transition":{"menu_item":"fadeInDown","post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":-1,"unescape":false,"preload":false}}</script><script src="/js/config.js"></script>

    <meta name="description" content="二叉树二叉树第K小给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。 1.返回第k小的节点值即可 2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1 3.保证n个节点的值不一样 12345678910111213141516171819202122232425262728class Solution &amp;#123;public:     int">
<meta property="og:type" content="article">
<meta property="og:title" content="一些还不错的题-4">
<meta property="og:url" content="http://example.com/2022/07/20/%E4%B8%80%E4%BA%9B%E8%BF%98%E4%B8%8D%E9%94%99%E7%9A%84%E9%A2%98-4/index.html">
<meta property="og:site_name" content="JsyBlog">
<meta property="og:description" content="二叉树二叉树第K小给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。 1.返回第k小的节点值即可 2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1 3.保证n个节点的值不一样 12345678910111213141516171819202122232425262728class Solution &amp;#123;public:     int">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2022-07-19T16:00:03.000Z">
<meta property="article:modified_time" content="2023-01-03T11:25:56.417Z">
<meta property="article:author" content="SongyangJi">
<meta name="twitter:card" content="summary">


<link rel="canonical" href="http://example.com/2022/07/20/%E4%B8%80%E4%BA%9B%E8%BF%98%E4%B8%8D%E9%94%99%E7%9A%84%E9%A2%98-4/">



<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"http://example.com/2022/07/20/%E4%B8%80%E4%BA%9B%E8%BF%98%E4%B8%8D%E9%94%99%E7%9A%84%E9%A2%98-4/","path":"2022/07/20/一些还不错的题-4/","title":"一些还不错的题-4"}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>一些还不错的题-4 | JsyBlog</title>
  








  <noscript>
    <link rel="stylesheet" href="/css/noscript.css">
  </noscript>
</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <div class="column">
      <header class="header" itemscope itemtype="http://schema.org/WPHeader"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <p class="site-title">JsyBlog</p>
      <i class="logo-line"></i>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger" aria-label="搜索" role="button">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li><li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup"><div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close" role="button">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</header>
        
  
  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="nav-number">1.</span> <span class="nav-text">二叉树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91%E7%AC%ACK%E5%B0%8F"><span class="nav-number">1.1.</span> <span class="nav-text">二叉树第K小</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#DP"><span class="nav-number">2.</span> <span class="nav-text">DP</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%89%94%E9%B8%A1%E8%9B%8B"><span class="nav-number">2.1.</span> <span class="nav-text">扔鸡蛋</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#NC122-%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%8C%B9%E9%85%8D"><span class="nav-number">2.2.</span> <span class="nav-text">NC122 正则表达式匹配</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#NC135-%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E5%A5%BD%E6%97%B6%E6%9C%BA-%E4%B8%89"><span class="nav-number">2.3.</span> <span class="nav-text">NC135 买卖股票的最好时机(三)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#NC167-%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E5%A5%BD%E6%97%B6%E6%9C%BA-%E5%9B%9B"><span class="nav-number">2.4.</span> <span class="nav-text">NC167 买卖股票的最好时机(四)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#NC44%E9%80%9A%E9%85%8D%E7%AC%A6%E5%8C%B9%E9%85%8D"><span class="nav-number">2.5.</span> <span class="nav-text">NC44通配符匹配</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#NC173-%E5%A1%AB%E5%85%85%E6%95%B0%E7%BB%84"><span class="nav-number">2.6.</span> <span class="nav-text">NC173 填充数组</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#NC178-%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D-%E4%B8%89"><span class="nav-number">2.7.</span> <span class="nav-text">NC178 打家劫舍(三)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#NC196-%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB-%E4%B8%80"><span class="nav-number">2.8.</span> <span class="nav-text">NC196 编辑距离(一)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#NC187-%E5%8E%8B%E7%BC%A9%E5%AD%97%E7%AC%A6%E4%B8%B2-%E4%BA%8C"><span class="nav-number">2.9.</span> <span class="nav-text">NC187 压缩字符串(二)</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%BA%8C%E5%88%86"><span class="nav-number">3.</span> <span class="nav-text">二分</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%B8%A4%E4%B8%AA%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E6%89%BEtopk"><span class="nav-number">3.1.</span> <span class="nav-text">两个有序数组找topk</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#NC164-%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97-%E4%BA%8C"><span class="nav-number">3.2.</span> <span class="nav-text">NC164 最长上升子序列(二)</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%9B%9E%E6%BA%AF"><span class="nav-number">4.</span> <span class="nav-text">回溯</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%95%B0%E7%8B%AC"><span class="nav-number">4.1.</span> <span class="nav-text">数独</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#NC182-%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86-%E4%BA%8C"><span class="nav-number">4.2.</span> <span class="nav-text">NC182 单词拆分(二)</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%A0%88"><span class="nav-number">5.</span> <span class="nav-text">栈</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#NC171-%E7%9B%B4%E6%96%B9%E5%9B%BE%E5%86%85%E6%9C%80%E5%A4%A7%E7%9F%A9%E5%BD%A2"><span class="nav-number">5.1.</span> <span class="nav-text">NC171 直方图内最大矩形</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#NC237-%E6%9C%80%E5%A4%A7%E7%9F%A9%E5%BD%A2"><span class="nav-number">5.2.</span> <span class="nav-text">NC237 最大矩形</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#NC240-%E8%AE%A1%E7%AE%97%E5%99%A8-%E4%B8%80"><span class="nav-number">5.3.</span> <span class="nav-text">NC240 计算器(一)</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%85%B6%E4%BB%96"><span class="nav-number">6.</span> <span class="nav-text">其他</span></a></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">SongyangJi</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/archives/">
          <span class="site-state-item-count">251</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
          <a href="/categories/">
        <span class="site-state-item-count">45</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
          <a href="/tags/">
        <span class="site-state-item-count">109</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>

        </div>
      </div>
    </div>

    
  </aside>


    </div>

    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://example.com/2022/07/20/%E4%B8%80%E4%BA%9B%E8%BF%98%E4%B8%8D%E9%94%99%E7%9A%84%E9%A2%98-4/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="SongyangJi">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="JsyBlog">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="一些还不错的题-4 | JsyBlog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          一些还不错的题-4
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2022-07-20 00:00:03" itemprop="dateCreated datePublished" datetime="2022-07-20T00:00:03+08:00">2022-07-20</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2023-01-03 19:25:56" itemprop="dateModified" datetime="2023-01-03T19:25:56+08:00">2023-01-03</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E7%AE%97%E6%B3%95%E9%A2%98/" itemprop="url" rel="index"><span itemprop="name">算法题</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <h2 id="二叉树"><a href="#二叉树" class="headerlink" title="二叉树"></a>二叉树</h2><h3 id="二叉树第K小"><a href="#二叉树第K小" class="headerlink" title="二叉树第K小"></a>二叉树第K小</h3><p>给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。</p>
<p>1.返回第k小的节点值即可</p>
<p>2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1</p>
<p>3.保证n个节点的值不一样</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>: </span><br><span class="line">    <span class="type">int</span> cnt = <span class="number">0</span>;</span><br><span class="line">    <span class="type">int</span> ans = <span class="number">-1</span>;</span><br><span class="line">    <span class="type">int</span> k;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">KthNode</span><span class="params">(TreeNode* proot, <span class="type">int</span> k)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(proot == <span class="literal">nullptr</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">this</span>-&gt;k = k;</span><br><span class="line">        <span class="built_in">dfs</span>(proot);</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">dfs</span><span class="params">(TreeNode* root)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(root == <span class="literal">nullptr</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">dfs</span>(root-&gt;left);</span><br><span class="line">        ++cnt;</span><br><span class="line">        <span class="keyword">if</span>(cnt == k) &#123;</span><br><span class="line">            ans = root-&gt;val;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">dfs</span>(root-&gt;right);</span><br><span class="line">    &#125;</span><br><span class="line">        </span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<h2 id="DP"><a href="#DP" class="headerlink" title="DP"></a>DP</h2><h3 id="扔鸡蛋"><a href="#扔鸡蛋" class="headerlink" title="扔鸡蛋"></a>扔鸡蛋</h3><p>时间复杂度：O(nk)&#x3D;O(nlogn)</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     * 返回最差情况下扔棋子的最小次数</span></span><br><span class="line"><span class="comment">     * @param n int整型 楼层数</span></span><br><span class="line"><span class="comment">     * @param k int整型 棋子数</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    状态：f[i][j] i个棋子，j层楼的操作系数</span></span><br><span class="line"><span class="comment">    转移：f[i][j] = 1 + max(f[i - 1][t - 1], f[i][j - t]) 枚举所有的t，找出最优的</span></span><br><span class="line"><span class="comment">    初始：f[1][j] = j;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    空间优化，i的维度只用到当前状态和前一个状态，所有可以使用滚动数组优化成f[j]</span></span><br><span class="line"><span class="comment">    时间优化，i确定的时候，f[i - 1][t - 1]随t单调增，f[i][j - t]随t单调减，临界点的寻找可以用单调性优化</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    */</span></span><br><span class="line"></span><br><span class="line">    <span class="type">const</span> <span class="type">int</span> N = <span class="number">1000010</span>;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">solve</span><span class="params">(<span class="type">int</span> n, <span class="type">int</span> k)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 优化性质, 如果k充分大, 二分的扔即可（有点投机取巧）</span></span><br><span class="line">        <span class="type">int</span> b = <span class="built_in">log2</span>(n) + <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">if</span>(k &gt;= <span class="built_in">log2</span>(n) + <span class="number">1</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> b;</span><br><span class="line">        &#125;</span><br><span class="line">        k = <span class="built_in">min</span>(k, n);</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="function">vector&lt;<span class="type">int</span>&gt; <span class="title">f0</span><span class="params">(N)</span>, <span class="title">f1</span><span class="params">(N)</span></span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 初始化</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt;= n; ++j) &#123;</span><br><span class="line">            f0[j] = j;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">2</span>; i &lt;= k; ++i) &#123;</span><br><span class="line">            <span class="type">int</span> tt = <span class="number">1</span>; <span class="comment">// 临界点逐渐递增</span></span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>; j &lt;= n; j++) &#123;</span><br><span class="line">                <span class="type">int</span> res = inf;</span><br><span class="line"><span class="comment">//                原始版本                </span></span><br><span class="line"><span class="comment">//                for(int t = j; t &gt;= tt; --t) &#123;</span></span><br><span class="line"><span class="comment">//                    res = min(res, max(f0[t - 1], f1[j - t]) + 1);</span></span><br><span class="line"><span class="comment">//                &#125;</span></span><br><span class="line">                <span class="keyword">while</span> (tt &lt;= j &amp;&amp; f0[tt - <span class="number">1</span>] &lt; f1[j - tt]) &#123;</span><br><span class="line">                    ++tt;</span><br><span class="line">                &#125;</span><br><span class="line">                res = f1[j - (tt - <span class="number">1</span>)];</span><br><span class="line">                <span class="keyword">if</span>(tt &lt;= j) res = <span class="built_in">min</span>(res, f0[tt - <span class="number">1</span>]);</span><br><span class="line">                f1[j] = res + <span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            f0 = f1;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> f0[n];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br></pre></td></tr></table></figure>


<blockquote>
<p>题解</p>
<p><a target="_blank" rel="noopener" href="https://song-yang-ji.blog.csdn.net/article/details/121206001">https://song-yang-ji.blog.csdn.net/article/details/121206001</a></p>
<p><a target="_blank" rel="noopener" href="https://blog.nowcoder.net/n/702aa052fefb4b7d8e2949874c52316a?f=comment">https://blog.nowcoder.net/n/702aa052fefb4b7d8e2949874c52316a?f=comment</a></p>
</blockquote>
<h3 id="NC122-正则表达式匹配"><a href="#NC122-正则表达式匹配" class="headerlink" title="NC122 正则表达式匹配"></a>NC122 正则表达式匹配</h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4?tpId=117&tqId=37780&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=50&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4?tpId=117&amp;tqId=37780&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param str string字符串</span></span><br><span class="line"><span class="comment">     * @param pattern string字符串</span></span><br><span class="line"><span class="comment">     * @return bool布尔型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">match</span><span class="params">(string s, string p)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (p[<span class="number">0</span>] == <span class="string">&#x27;*&#x27;</span>) &#123; <span class="comment">// assert</span></span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> m = s.<span class="built_in">length</span>();</span><br><span class="line">        <span class="type">int</span> n = p.<span class="built_in">length</span>();</span><br><span class="line">        s = <span class="string">&quot; &quot;</span> + s;</span><br><span class="line">        p = <span class="string">&quot; &quot;</span> + p;</span><br><span class="line">        vector&lt;vector&lt;<span class="type">bool</span>&gt; &gt; <span class="built_in">f</span>(m + <span class="number">10</span>, <span class="built_in">vector</span>&lt;<span class="type">bool</span>&gt;(n + <span class="number">10</span>));</span><br><span class="line">        f[<span class="number">0</span>][<span class="number">0</span>] = <span class="literal">true</span>;</span><br><span class="line">        <span class="comment">// key: i start from 0</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt;= m; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">1</span>; j &lt;= n; ++j) &#123;</span><br><span class="line">                <span class="keyword">if</span> (p[j] == <span class="string">&#x27;*&#x27;</span>) &#123; <span class="comment">// assert j &gt;= 2</span></span><br><span class="line">                    <span class="type">char</span> c = p[j - <span class="number">1</span>];</span><br><span class="line">                    <span class="keyword">if</span> (f[i][j - <span class="number">2</span>]) &#123; <span class="comment">// 一次不用</span></span><br><span class="line">                        f[i][j] = <span class="literal">true</span>;</span><br><span class="line">                    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                        <span class="type">int</span> k = <span class="number">0</span>;</span><br><span class="line">                        <span class="keyword">while</span> (i &gt; k &amp;&amp; (c == <span class="string">&#x27;.&#x27;</span> || s[i - k] == c)) &#123;</span><br><span class="line">                            <span class="keyword">if</span> (f[i - k - <span class="number">1</span>][j - <span class="number">2</span>]) &#123;</span><br><span class="line">                                f[i][j] = <span class="literal">true</span>;</span><br><span class="line">                                <span class="keyword">break</span>;</span><br><span class="line">                            &#125;</span><br><span class="line">                            ++k;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                    <span class="keyword">if</span> (i &gt; <span class="number">0</span> &amp;&amp; f[i - <span class="number">1</span>][j - <span class="number">1</span>] &amp;&amp; (s[i] == p[j] || p[j] == <span class="string">&#x27;.&#x27;</span>)) &#123;</span><br><span class="line">                        f[i][j] = <span class="literal">true</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> f[m][n];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<p>更优秀的写法：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="type">bool</span> f[<span class="number">30</span>][<span class="number">40</span>] = &#123;<span class="number">0</span>&#125;;</span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">isMatch</span><span class="params">(string s, string p)</span> </span>&#123;</span><br><span class="line">        <span class="type">int</span> m = s.<span class="built_in">size</span>(), n = p.<span class="built_in">size</span>();</span><br><span class="line">        s = <span class="string">&quot; &quot;</span> + s;</span><br><span class="line">        p = <span class="string">&quot; &quot;</span> + p;</span><br><span class="line">        f[<span class="number">0</span>][<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">auto</span> ok = [&amp;](<span class="type">int</span> i, <span class="type">int</span> j) &#123;</span><br><span class="line">            <span class="keyword">if</span>(i == <span class="number">0</span> || j == <span class="number">0</span>) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">            <span class="keyword">return</span> p[j] == <span class="string">&#x27;.&#x27;</span> || s[i] == p[j];</span><br><span class="line">        &#125;;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt;= m; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>; j &lt;= n; j++) &#123;</span><br><span class="line">                <span class="keyword">if</span>(p[j] == <span class="string">&#x27;*&#x27;</span>) &#123;</span><br><span class="line">                    f[i][j] = f[i][j - <span class="number">2</span>]; <span class="comment">// 题给数据保证不越界</span></span><br><span class="line">                    <span class="keyword">if</span>(<span class="built_in">ok</span>(i, j - <span class="number">1</span>)) &#123;</span><br><span class="line">                        f[i][j] |= f[i - <span class="number">1</span>][j]; <span class="comment">// key</span></span><br><span class="line">                    &#125;</span><br><span class="line">                &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                    f[i][j] = <span class="built_in">ok</span>(i, j) ? f[i - <span class="number">1</span>][j - <span class="number">1</span>] : <span class="literal">false</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> f[m][n];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br></pre></td></tr></table></figure>





<blockquote>
<p>题解</p>
<p><a target="_blank" rel="noopener" href="https://song-yang-ji.blog.csdn.net/article/details/121688339">https://song-yang-ji.blog.csdn.net/article/details/121688339</a></p>
</blockquote>
<h3 id="NC135-买卖股票的最好时机-三"><a href="#NC135-买卖股票的最好时机-三" class="headerlink" title="NC135 买卖股票的最好时机(三)"></a>NC135 买卖股票的最好时机(三)</h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/4892d3ff304a4880b7a89ba01f48daf9?tpId=117&tqId=37847&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/4892d3ff304a4880b7a89ba01f48daf9?tpId=117&amp;tqId=37847&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">100010</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> inf = <span class="number">0x3f3f3f3f</span>;</span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     * 两次交易所能获得的最大收益</span></span><br><span class="line"><span class="comment">     * @param prices int整型vector 股票每一天的价格</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">maxProfit</span><span class="params">(vector&lt;<span class="type">int</span>&gt;&amp; a)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="type">int</span> n = a.<span class="built_in">size</span>();</span><br><span class="line">        <span class="type">int</span> f[N][<span class="number">3</span>][<span class="number">2</span>] = &#123;<span class="number">0</span>&#125;;</span><br><span class="line">        <span class="comment">// 初始化</span></span><br><span class="line">        f[<span class="number">0</span>][<span class="number">0</span>][<span class="number">1</span>] = -a[<span class="number">0</span>];</span><br><span class="line">        f[<span class="number">0</span>][<span class="number">1</span>][<span class="number">0</span>] = -inf;</span><br><span class="line">        f[<span class="number">0</span>][<span class="number">1</span>][<span class="number">1</span>] = -inf;</span><br><span class="line">        f[<span class="number">0</span>][<span class="number">2</span>][<span class="number">0</span>] = -inf;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt; n; ++i) &#123;</span><br><span class="line">            f[i][<span class="number">0</span>][<span class="number">1</span>] = <span class="built_in">max</span>(f[i - <span class="number">1</span>][<span class="number">0</span>][<span class="number">1</span>], f[i - <span class="number">1</span>][<span class="number">0</span>][<span class="number">0</span>] - a[i]);</span><br><span class="line">            f[i][<span class="number">1</span>][<span class="number">0</span>] = <span class="built_in">max</span>(f[i - <span class="number">1</span>][<span class="number">1</span>][<span class="number">0</span>], f[i - <span class="number">1</span>][<span class="number">0</span>][<span class="number">1</span>] + a[i]);</span><br><span class="line">            f[i][<span class="number">1</span>][<span class="number">1</span>] = <span class="built_in">max</span>(f[i - <span class="number">1</span>][<span class="number">1</span>][<span class="number">1</span>], f[i - <span class="number">1</span>][<span class="number">1</span>][<span class="number">0</span>] - a[i]);</span><br><span class="line">            f[i][<span class="number">2</span>][<span class="number">0</span>] = <span class="built_in">max</span>(f[i - <span class="number">1</span>][<span class="number">2</span>][<span class="number">0</span>], f[i - <span class="number">1</span>][<span class="number">1</span>][<span class="number">1</span>] + a[i]);</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">        <span class="type">int</span> ans = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; <span class="number">3</span>; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">0</span>; j &lt; <span class="number">2</span>; ++j) &#123;</span><br><span class="line">                ans = <span class="built_in">max</span>(ans, f[n - <span class="number">1</span>][i][j]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h3 id="NC167-买卖股票的最好时机-四"><a href="#NC167-买卖股票的最好时机-四" class="headerlink" title="NC167 买卖股票的最好时机(四)"></a><strong>NC167</strong> <strong>买卖股票的最好时机(四)</strong></h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/1c583d416d504b80821fbe4cc20404f3?tpId=117&tqId=39309&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/1c583d416d504b80821fbe4cc20404f3?tpId=117&amp;tqId=39309&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param prices int整型vector</span></span><br><span class="line"><span class="comment">     * @param k int整型</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">maxProfit</span><span class="params">(vector&lt;<span class="type">int</span>&gt; &amp;a, <span class="type">int</span> K)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="type">int</span> n = a.<span class="built_in">size</span>();</span><br><span class="line">        vector&lt;vector&lt;vector&lt;<span class="type">int</span>&gt;&gt;&gt; <span class="built_in">f</span>(n + <span class="number">10</span>, vector&lt;vector&lt;<span class="type">int</span>&gt;&gt;(K + <span class="number">1</span>, <span class="built_in">vector</span>&lt;<span class="type">int</span>&gt;(<span class="number">2</span>, -inf)));</span><br><span class="line">        <span class="comment">// init</span></span><br><span class="line">        f[<span class="number">0</span>][<span class="number">0</span>][<span class="number">0</span>] = <span class="number">0</span>;</span><br><span class="line">        f[<span class="number">0</span>][<span class="number">0</span>][<span class="number">1</span>] = -a[<span class="number">0</span>];</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt; n; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> k = <span class="number">0</span>; k &lt;= K; ++k) &#123;</span><br><span class="line">                f[i][k][<span class="number">0</span>] = <span class="built_in">max</span>(f[i - <span class="number">1</span>][k][<span class="number">0</span>], k &gt; <span class="number">0</span> ? (f[i - <span class="number">1</span>][k - <span class="number">1</span>][<span class="number">1</span>] + a[i]) : -inf);</span><br><span class="line">                f[i][k][<span class="number">1</span>] = <span class="built_in">max</span>(f[i - <span class="number">1</span>][k][<span class="number">1</span>], f[i - <span class="number">1</span>][k][<span class="number">0</span>] - a[i]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> ans = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt;= K; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; <span class="number">2</span>; j++) &#123;</span><br><span class="line">                ans = <span class="built_in">max</span>(ans, f[n - <span class="number">1</span>][i][j]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<h3 id="NC44通配符匹配"><a href="#NC44通配符匹配" class="headerlink" title="NC44通配符匹配"></a>NC44通配符匹配</h3><p>时间复杂度：O(m*n)</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">isMatch</span><span class="params">(<span class="type">const</span> <span class="type">char</span> *ps, <span class="type">const</span> <span class="type">char</span> *pp)</span> </span>&#123;</span><br><span class="line">        <span class="type">int</span> m = <span class="built_in">strlen</span>(ps);</span><br><span class="line">        <span class="type">int</span> n = <span class="built_in">strlen</span>(pp);</span><br><span class="line">        string s = <span class="string">&quot; &quot;</span> + <span class="built_in">string</span>(ps);</span><br><span class="line">        string p = <span class="string">&quot; &quot;</span> + <span class="built_in">string</span>(pp);</span><br><span class="line">        vector&lt;vector&lt;<span class="type">bool</span>&gt;&gt; <span class="built_in">f</span>(m + <span class="number">10</span>, <span class="built_in">vector</span>&lt;<span class="type">bool</span>&gt;(n + <span class="number">10</span>));</span><br><span class="line">        f[<span class="number">0</span>][<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt;= m; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">1</span>; j &lt;= n; ++j) &#123;</span><br><span class="line">                <span class="keyword">if</span> (p[j] == <span class="string">&#x27;*&#x27;</span>) &#123;</span><br><span class="line">                    f[i][j] = f[i][j - <span class="number">1</span>] || (i &gt; <span class="number">0</span> &amp;&amp; f[i - <span class="number">1</span>][j]);</span><br><span class="line">                &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                    <span class="keyword">if</span> (i &gt; <span class="number">0</span> &amp;&amp; (s[i] == p[j] || p[j] == <span class="string">&#x27;?&#x27;</span>)) &#123;</span><br><span class="line">                        f[i][j] = f[i - <span class="number">1</span>][j - <span class="number">1</span>];</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> f[m][n];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<p>todo:</p>
<p>空间复杂度 O(1)，时间复杂度 O(n)</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>





<h3 id="NC173-填充数组"><a href="#NC173-填充数组" class="headerlink" title="NC173 填充数组"></a><strong>NC173</strong> <strong>填充数组</strong></h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/3e34d9ed0bbc4db68b6fbca20a62926d?tpId=117&tqId=39329&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/3e34d9ed0bbc4db68b6fbca20a62926d?tpId=117&amp;tqId=39329&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<p><strong>计数DP</strong></p>
<p>加法原理</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">const</span> <span class="type">int</span> MOD = <span class="number">1e9</span> + <span class="number">7</span>; </span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * </span></span><br><span class="line"><span class="comment">     * @param a int整型vector </span></span><br><span class="line"><span class="comment">     * @param k int整型 </span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">FillArray</span><span class="params">(vector&lt;<span class="type">int</span>&gt;&amp; a, <span class="type">int</span> K)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="type">int</span> n = a.<span class="built_in">size</span>();</span><br><span class="line">        vector&lt;vector&lt;<span class="type">int</span>&gt;&gt; <span class="built_in">f</span>(n + <span class="number">10</span>, <span class="built_in">vector</span>&lt;<span class="type">int</span>&gt;(K + <span class="number">10</span>));</span><br><span class="line">        <span class="comment">// init</span></span><br><span class="line">        <span class="keyword">if</span>(a[<span class="number">0</span>]) &#123;</span><br><span class="line">            f[<span class="number">0</span>][a[<span class="number">0</span>]] = <span class="number">1</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> k = <span class="number">1</span>; k &lt;= K; ++k) &#123;</span><br><span class="line">                f[<span class="number">0</span>][k] = <span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt; n; ++i) &#123;</span><br><span class="line">            <span class="type">int</span> tmp = <span class="number">0</span>;</span><br><span class="line">            <span class="keyword">if</span>(a[i]) &#123;</span><br><span class="line">                <span class="keyword">for</span>(<span class="type">int</span> k = <span class="number">1</span>; k &lt;= a[i]; ++k) &#123;</span><br><span class="line">                    tmp = (tmp + f[i - <span class="number">1</span>][k]) % MOD;</span><br><span class="line">                &#125;</span><br><span class="line">                f[i][a[i]] = tmp;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="keyword">for</span>(<span class="type">int</span> k = <span class="number">1</span>; k &lt;= K; ++k) &#123;</span><br><span class="line">                    tmp = (tmp + f[i - <span class="number">1</span>][k]) % MOD;</span><br><span class="line">                    f[i][k] = tmp;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> ans = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> k = <span class="number">1</span>; k &lt;= K; ++k) &#123;</span><br><span class="line">            ans = (ans + f[n - <span class="number">1</span>][k]) % MOD;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h3 id="NC178-打家劫舍-三"><a href="#NC178-打家劫舍-三" class="headerlink" title="NC178 打家劫舍(三)"></a><strong>NC178</strong> <strong>打家劫舍(三)</strong></h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/82b6dce6a7634419b272ee4397e26d89?tpId=117&tqId=39334&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/82b6dce6a7634419b272ee4397e26d89?tpId=117&amp;tqId=39334&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param root TreeNode类</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    unordered_map&lt;TreeNode *, unordered_map&lt;<span class="type">bool</span>, <span class="type">int</span>&gt;&gt; dp;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">rob</span><span class="params">(TreeNode *root)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">max</span>(<span class="built_in">help</span>(root-&gt;left, <span class="literal">false</span>) + <span class="built_in">help</span>(root-&gt;right, <span class="literal">false</span>),</span><br><span class="line">                   root-&gt;val + <span class="built_in">help</span>(root-&gt;left, <span class="literal">true</span>) + <span class="built_in">help</span>(root-&gt;right, <span class="literal">true</span>));</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">help</span><span class="params">(TreeNode *root, <span class="type">bool</span> pick)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="literal">nullptr</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">if</span>(dp[root][pick]) <span class="keyword">return</span> dp[root][pick];</span><br><span class="line">        <span class="type">int</span> res = <span class="built_in">help</span>(root-&gt;left, <span class="literal">false</span>) + <span class="built_in">help</span>(root-&gt;right, <span class="literal">false</span>);</span><br><span class="line">        <span class="keyword">if</span> (!pick) &#123;</span><br><span class="line">            res = <span class="built_in">max</span>(res, root-&gt;val + <span class="built_in">help</span>(root-&gt;left, <span class="literal">true</span>) + <span class="built_in">help</span>(root-&gt;right, <span class="literal">true</span>));</span><br><span class="line">        &#125;</span><br><span class="line">        dp[root][pick] = res;</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<p>或者更好的：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    unordered_map&lt;TreeNode *, <span class="type">int</span>&gt; mp1, mp2;<span class="comment">//mp1,mp2分别表示当前节点偷或不偷的最大金额</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">rob</span><span class="params">(TreeNode *root)</span> </span>&#123;</span><br><span class="line">        <span class="built_in">f</span>(root);<span class="comment">//递归</span></span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">max</span>(mp1[root], mp2[root]);<span class="comment">//返回最大值</span></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">f</span><span class="params">(TreeNode *root)</span> </span>&#123;<span class="comment">//递归</span></span><br><span class="line">        <span class="keyword">if</span> (root == <span class="literal">nullptr</span>)</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        <span class="built_in">f</span>(root-&gt;left);<span class="comment">//左递归</span></span><br><span class="line">        <span class="built_in">f</span>(root-&gt;right);<span class="comment">//右递归</span></span><br><span class="line">        mp1[root] = root-&gt;val + mp2[root-&gt;left] + mp2[root-&gt;right];<span class="comment">//当前节点偷</span></span><br><span class="line">        mp2[root] = <span class="built_in">max</span>(mp1[root-&gt;left], mp2[root-&gt;left]) + <span class="built_in">max</span>(mp1[root-&gt;right], mp2[root-&gt;right]);<span class="comment">//当前节点不偷</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<h3 id="NC196-编辑距离-一"><a href="#NC196-编辑距离-一" class="headerlink" title="NC196 编辑距离(一)"></a><strong>NC196</strong> <strong>编辑距离(一)</strong></h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da?tpId=117&tqId=39371&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da?tpId=117&amp;tqId=39371&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">1010</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> INF = <span class="number">0x3f3f3f3f</span>;</span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * </span></span><br><span class="line"><span class="comment">     * @param str1 string字符串 </span></span><br><span class="line"><span class="comment">     * @param str2 string字符串 </span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">editDistance</span><span class="params">(string s1, string s2)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="type">int</span> f[N][N];</span><br><span class="line">        <span class="built_in">memset</span>(f, INF, <span class="built_in">sizeof</span>(f));</span><br><span class="line">        <span class="type">int</span> m = s1.<span class="built_in">size</span>();</span><br><span class="line">        <span class="type">int</span> n = s2.<span class="built_in">size</span>();</span><br><span class="line">        s1 = <span class="string">&quot; &quot;</span> + s1;</span><br><span class="line">        s2 = <span class="string">&quot; &quot;</span> + s2;</span><br><span class="line">        f[<span class="number">0</span>][<span class="number">0</span>] = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>; j &lt;= n; ++j) &#123;</span><br><span class="line">            f[<span class="number">0</span>][j] = j; <span class="comment">// add</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= m; ++i) &#123;</span><br><span class="line">            f[i][<span class="number">0</span>] = i; <span class="comment">// del</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= m; ++i) &#123; <span class="comment">// key</span></span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>; j &lt;= n; ++j) &#123;</span><br><span class="line">                <span class="type">int</span> res = INF;</span><br><span class="line">                res = f[i - <span class="number">1</span>][j - <span class="number">1</span>] + ((s1[i] == s2[j]) ? <span class="number">0</span> : <span class="number">1</span>);</span><br><span class="line">                res = <span class="built_in">min</span>(res, f[i][j - <span class="number">1</span>] + <span class="number">1</span>); <span class="comment">// add</span></span><br><span class="line">                res = <span class="built_in">min</span>(res, f[i - <span class="number">1</span>][j] + <span class="number">1</span>); <span class="comment">// del</span></span><br><span class="line">                f[i][j] = res;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> f[m][n];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h3 id="NC187-压缩字符串-二"><a href="#NC187-压缩字符串-二" class="headerlink" title="NC187 压缩字符串(二)"></a><strong>NC187</strong> <strong>压缩字符串(二)</strong></h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/2724df81a7d94b70932d96b759848f0a?tpId=117&tqId=39354&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/2724df81a7d94b70932d96b759848f0a?tpId=117&amp;tqId=39354&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> ll long long</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> ull unsigned long long</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param s string字符串</span></span><br><span class="line"><span class="comment">     * @param k int整型</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="type">int</span> f[<span class="number">110</span>][<span class="number">110</span>];</span><br><span class="line">    <span class="type">int</span> n;</span><br><span class="line">    string s;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">compressString</span><span class="params">(string s, <span class="type">int</span> k)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        n = s.<span class="built_in">length</span>();</span><br><span class="line">        <span class="keyword">this</span>-&gt;s = s;</span><br><span class="line">        <span class="keyword">if</span> (n == <span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="built_in">memset</span>(f, inf, <span class="keyword">sizeof</span> f);</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">dfs</span>(<span class="number">0</span>, k);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">trans</span><span class="params">(<span class="type">int</span> num)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (num == <span class="number">1</span>) <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">        string numStr = <span class="built_in">to_string</span>(num);</span><br><span class="line">        <span class="keyword">return</span> numStr.<span class="built_in">length</span>() + <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">dfs</span><span class="params">(<span class="type">int</span> idx, <span class="type">int</span> k)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (idx == n) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="type">int</span> &amp;res = f[idx][k];</span><br><span class="line">        <span class="keyword">if</span> (res != inf) <span class="keyword">return</span> res;</span><br><span class="line">        <span class="keyword">if</span> (k) res = <span class="built_in">dfs</span>(idx + <span class="number">1</span>, k - <span class="number">1</span>);</span><br><span class="line">        <span class="type">char</span> c = s[idx];</span><br><span class="line">        <span class="type">int</span> same = <span class="number">0</span>, diff = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = idx; i &lt; n; ++i) &#123;</span><br><span class="line">            <span class="keyword">if</span> (c == s[i]) &#123;</span><br><span class="line">                ++same;</span><br><span class="line">                res = <span class="built_in">min</span>(res, <span class="built_in">trans</span>(same) + <span class="built_in">dfs</span>(i + <span class="number">1</span>, k - diff));</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                res = <span class="built_in">min</span>(res, <span class="built_in">trans</span>(same) + <span class="built_in">dfs</span>(i, k - diff));</span><br><span class="line">                ++diff;</span><br><span class="line">                <span class="keyword">if</span> (diff &gt; k) <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * </span></span><br><span class="line"><span class="comment">     * @param s string字符串 </span></span><br><span class="line"><span class="comment">     * @param k int整型 </span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="type">int</span> f[<span class="number">110</span>][<span class="number">110</span>];</span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">compressString</span><span class="params">(string s, <span class="type">int</span> K)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="type">int</span> n = s.<span class="built_in">size</span>();</span><br><span class="line">        <span class="built_in">memset</span>(f, inf, <span class="built_in">sizeof</span>(f));</span><br><span class="line">        s = <span class="string">&quot; &quot;</span> + s;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> k = <span class="number">0</span>; k &lt;= K; ++k) f[<span class="number">0</span>][k] = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> k = <span class="number">0</span>; k &lt;= K; ++k) &#123;</span><br><span class="line">                <span class="type">int</span> &amp;res = f[i][k];</span><br><span class="line">                <span class="keyword">if</span>(k) res = <span class="built_in">min</span>(res, f[i - <span class="number">1</span>][k - <span class="number">1</span>]);</span><br><span class="line">                <span class="type">int</span> same = <span class="number">0</span>, diff = <span class="number">0</span>;</span><br><span class="line">                <span class="keyword">for</span>(<span class="type">int</span> idx = i; idx &gt;= <span class="number">1</span>; --idx) &#123;</span><br><span class="line">                    <span class="keyword">if</span>(s[i] == s[idx]) &#123;</span><br><span class="line">                        ++same;</span><br><span class="line">                        res = <span class="built_in">min</span>(res, <span class="built_in">cal</span>(same) + f[idx - <span class="number">1</span>][k - diff]);</span><br><span class="line">                    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                        ++diff;</span><br><span class="line">                        <span class="keyword">if</span>(diff &gt; k) <span class="keyword">break</span>;</span><br><span class="line">                        res = <span class="built_in">min</span>(res, <span class="built_in">cal</span>(same) + f[idx - <span class="number">1</span>][k - diff]);</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> f[n][K];</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">cal</span><span class="params">(<span class="type">int</span> count)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(count == <span class="number">1</span>) <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">        string s = <span class="built_in">to_string</span>(count);</span><br><span class="line">        <span class="keyword">return</span> s.<span class="built_in">size</span>() + <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<h2 id="二分"><a href="#二分" class="headerlink" title="二分"></a>二分</h2><h3 id="两个有序数组找topk"><a href="#两个有序数组找topk" class="headerlink" title="两个有序数组找topk"></a>两个有序数组找topk</h3><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * find median in two sorted array</span></span><br><span class="line"><span class="comment">     * @param arr1 int整型vector the array1</span></span><br><span class="line"><span class="comment">     * @param arr2 int整型vector the array2</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">getK</span><span class="params">(<span class="type">int</span> k, vector&lt;<span class="type">int</span>&gt;&amp; a1, vector&lt;<span class="type">int</span>&gt;&amp; a2)</span> </span>&#123;</span><br><span class="line">        <span class="type">int</span> idx1 = <span class="number">0</span>, idx2 = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span>(k) &#123;</span><br><span class="line">            <span class="keyword">if</span>(idx1 &gt;= a1.<span class="built_in">size</span>()) &#123;</span><br><span class="line">                <span class="keyword">return</span> a2[idx2 + k - <span class="number">1</span>];</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(idx2 &gt;= a2.<span class="built_in">size</span>()) &#123;</span><br><span class="line">                <span class="keyword">return</span> a1[idx1 + k - <span class="number">1</span>];</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(k == <span class="number">1</span>) &#123;</span><br><span class="line">                <span class="keyword">return</span> (<span class="built_in">min</span>(a1[idx1], a2[idx2]));</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// k &gt;= 2</span></span><br><span class="line">            <span class="type">int</span> kk = k/<span class="number">2</span>;</span><br><span class="line">            <span class="type">int</span> del = <span class="number">0</span>;</span><br><span class="line">            <span class="type">int</span> newIdx1 = <span class="built_in">min</span>((<span class="type">int</span>)a1.<span class="built_in">size</span>(), idx1 + kk) - <span class="number">1</span>; <span class="comment">// 最后一个被del的元素的脚标</span></span><br><span class="line">            <span class="type">int</span> newIdx2 = <span class="built_in">min</span>((<span class="type">int</span>)a2.<span class="built_in">size</span>(), idx2 + kk) - <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">if</span>(a1[newIdx1] &lt; a2[newIdx2]) &#123;</span><br><span class="line">                del = newIdx1 - idx1 + <span class="number">1</span>;</span><br><span class="line">                idx1 = newIdx1 + <span class="number">1</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                del = newIdx2 - idx2 + <span class="number">1</span>;</span><br><span class="line">                idx2 = newIdx2 + <span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            k -= del;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">findMedianinTwoSortedAray</span><span class="params">(vector&lt;<span class="type">int</span>&gt;&amp; arr1, vector&lt;<span class="type">int</span>&gt;&amp; arr2)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">getK</span>(arr1.<span class="built_in">size</span>(), arr1, arr2);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h3 id="NC164-最长上升子序列-二"><a href="#NC164-最长上升子序列-二" class="headerlink" title="NC164 最长上升子序列(二)"></a><strong>NC164</strong> <strong>最长上升子序列(二)</strong></h3><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * 该数组最长严格上升子序列的长度</span></span><br><span class="line"><span class="comment">     * @param a int整型vector 给定的数组</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">LIS</span><span class="params">(vector&lt;<span class="type">int</span>&gt;&amp; a)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        vector&lt;<span class="type">int</span>&gt; res;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> x: a) &#123;</span><br><span class="line">            <span class="keyword">if</span>(res.<span class="built_in">empty</span>() || x &gt; res.<span class="built_in">back</span>()) &#123;</span><br><span class="line">                res.<span class="built_in">push_back</span>(x);</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="type">int</span> idx = <span class="built_in">upper_bound</span>(res.<span class="built_in">begin</span>(), res.<span class="built_in">end</span>(), x) - res.<span class="built_in">begin</span>();</span><br><span class="line">                res[idx] = x;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> res.<span class="built_in">size</span>();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<h2 id="回溯"><a href="#回溯" class="headerlink" title="回溯"></a>回溯</h2><h3 id="数独"><a href="#数独" class="headerlink" title="数独"></a>数独</h3><p>NC47 数独</p>
<p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/5e6c424b82224b85b64f28fd85761280?tpId=117&tqId=37743&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/5e6c424b82224b85b64f28fd85761280?tpId=117&amp;tqId=37743&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line">    <span class="type">const</span> <span class="type">static</span> <span class="type">int</span> N = <span class="number">9</span>;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="type">int</span> choice[N][N] = &#123;<span class="number">0</span>&#125;;</span><br><span class="line">    vector&lt;vector&lt;<span class="type">char</span>&gt; &gt; g;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">solveSudoku</span><span class="params">(vector&lt;vector&lt;<span class="type">char</span>&gt; &gt; &amp;board)</span> </span>&#123;</span><br><span class="line">        g = board;</span><br><span class="line">        <span class="keyword">if</span>(<span class="built_in">ok</span>()) <span class="keyword">return</span>;</span><br><span class="line">        pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt; p = <span class="built_in">pickBestPoint</span>();</span><br><span class="line">        <span class="built_in">dfs</span>(p.first, p.second);</span><br><span class="line">        board = g;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">dfs</span><span class="params">(<span class="type">int</span> x, <span class="type">int</span> y)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(x == <span class="number">-1</span>) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        vector&lt;<span class="type">char</span>&gt; cs = <span class="built_in">calChoice</span>(x, y);</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">char</span> c: cs) &#123;</span><br><span class="line">            g[x][y] = c;</span><br><span class="line">            <span class="keyword">if</span>(<span class="built_in">ok</span>()) <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">            pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt; p = <span class="built_in">pickBestPoint</span>();</span><br><span class="line">            <span class="keyword">if</span>(<span class="built_in">dfs</span>(p.first, p.second)) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        g[x][y] = <span class="string">&#x27;.&#x27;</span>; <span class="comment">// key</span></span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">ok</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; N; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; N; ++j) &#123;</span><br><span class="line">                <span class="keyword">if</span>(g[i][j] == <span class="string">&#x27;.&#x27;</span>) &#123;</span><br><span class="line">                    <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function">pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt; <span class="title">pickBestPoint</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="built_in">calChoice</span>();</span><br><span class="line">        <span class="type">int</span> m = <span class="number">10</span>;</span><br><span class="line">        pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt; p&#123;<span class="number">-1</span>, <span class="number">-1</span>&#125;;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; N; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; N; ++j) &#123;</span><br><span class="line">                <span class="keyword">if</span>(g[i][j] == <span class="string">&#x27;.&#x27;</span>) &#123;</span><br><span class="line">                    <span class="keyword">if</span> (choice[i][j] &lt; m) &#123;</span><br><span class="line">                        m = choice[i][j];</span><br><span class="line">                        p = <span class="built_in">make_pair</span>(i, j);</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> p;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">calChoice</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; N; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; N; ++j) &#123;</span><br><span class="line">                choice[i][j] = <span class="built_in">calChoice</span>(i, j).<span class="built_in">size</span>();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function">vector&lt;<span class="type">char</span>&gt; <span class="title">calChoice</span><span class="params">(<span class="type">int</span> x, <span class="type">int</span> y)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (g[x][y] != <span class="string">&#x27;.&#x27;</span>) <span class="keyword">return</span> &#123;&#125;;</span><br><span class="line">        set&lt;<span class="type">char</span>&gt; st;</span><br><span class="line">        <span class="comment">// row</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; N; ++j) &#123;</span><br><span class="line">            st.<span class="built_in">insert</span>(g[x][j]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// col</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; N; ++i) &#123;</span><br><span class="line">            st.<span class="built_in">insert</span>(g[i][y]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// box</span></span><br><span class="line">        x = (x / <span class="number">3</span>) * <span class="number">3</span>;</span><br><span class="line">        y = (y / <span class="number">3</span>) * <span class="number">3</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; <span class="number">3</span>; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; <span class="number">3</span>; ++j) &#123;</span><br><span class="line">                st.<span class="built_in">insert</span>(g[x + i][y + j]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        vector&lt;<span class="type">char</span>&gt; ans;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">char</span> c = <span class="string">&#x27;1&#x27;</span>; c &lt;= <span class="string">&#x27;9&#x27;</span>; ++c) &#123;</span><br><span class="line">            <span class="keyword">if</span> (st.<span class="built_in">find</span>(c) == st.<span class="built_in">end</span>()) &#123;</span><br><span class="line">                ans.<span class="built_in">push_back</span>(c);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<p>更简洁的写法：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">solveSudoku</span><span class="params">(vector&lt;vector&lt;<span class="type">char</span>&gt; &gt; &amp;board)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (!board.<span class="built_in">size</span>() || !board[<span class="number">0</span>].<span class="built_in">size</span>()) </span><br><span class="line">            <span class="keyword">return</span>; </span><br><span class="line">        <span class="built_in">helper</span>(board); </span><br><span class="line">        <span class="keyword">return</span>; </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">judgeValid</span><span class="params">(vector&lt;vector&lt;<span class="type">char</span>&gt; &gt; &amp;board, <span class="type">int</span> target, <span class="type">int</span> row, <span class="type">int</span> col)</span> </span>&#123;</span><br><span class="line">        <span class="type">char</span> ch = target + <span class="string">&#x27;0&#x27;</span>; </span><br><span class="line">        <span class="comment">// 判断每一行是否有效</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; board[<span class="number">0</span>].<span class="built_in">size</span>(); i ++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (board[row][i] == ch) </span><br><span class="line">                <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 判断每一列是否有效</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; board.<span class="built_in">size</span>(); i ++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (board[i][col] == ch) </span><br><span class="line">                <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 判断每一个方块是否有效</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = (row / <span class="number">3</span>) * <span class="number">3</span>; i &lt; (row / <span class="number">3</span>) * <span class="number">3</span> + <span class="number">3</span>; i ++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = (col / <span class="number">3</span>) * <span class="number">3</span>; j &lt; (col / <span class="number">3</span>) * <span class="number">3</span> + <span class="number">3</span>; j ++) &#123;</span><br><span class="line">                <span class="keyword">if</span> (board[i][j] == ch) </span><br><span class="line">                    <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">            &#125; </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>; </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">helper</span><span class="params">(vector&lt;vector&lt;<span class="type">char</span>&gt; &gt; &amp;board)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; board.<span class="built_in">size</span>(); i ++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; board[<span class="number">0</span>].<span class="built_in">size</span>(); j ++) &#123;</span><br><span class="line">                <span class="comment">// 如果已经被填写，则跳过</span></span><br><span class="line">                <span class="keyword">if</span> (board[i][j] != <span class="string">&#x27;.&#x27;</span>) </span><br><span class="line">                    <span class="keyword">continue</span>; </span><br><span class="line">                <span class="comment">// 从1至9进行遍历</span></span><br><span class="line">                <span class="keyword">for</span> (<span class="type">int</span> k = <span class="number">1</span>; k &lt;= <span class="number">9</span>; k ++) &#123;</span><br><span class="line">                    <span class="keyword">if</span> (<span class="built_in">judgeValid</span>(board, k, i, j)) &#123; <span class="comment">// 如果是有效的</span></span><br><span class="line">                        board[i][j] = (k + <span class="string">&#x27;0&#x27;</span>); </span><br><span class="line">                        <span class="keyword">if</span> (<span class="built_in">helper</span>(board)) <span class="comment">// 继续求解，并找到一个解</span></span><br><span class="line">                            <span class="keyword">return</span> <span class="literal">true</span>; </span><br><span class="line">                        <span class="keyword">else</span></span><br><span class="line">                            board[i][j] = <span class="string">&#x27;.&#x27;</span>;  <span class="comment">// 没能找到答案，重置</span></span><br><span class="line">                    &#125; </span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>; </span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h3 id="NC182-单词拆分-二"><a href="#NC182-单词拆分-二" class="headerlink" title="NC182 单词拆分(二)"></a><strong>NC182</strong> <strong>单词拆分(二)</strong></h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/bb40e0aae84a4491a35f93b322516cb5?tpId=117&tqId=39349&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/bb40e0aae84a4491a35f93b322516cb5?tpId=117&amp;tqId=39349&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param s string字符串</span></span><br><span class="line"><span class="comment">     * @param dic string字符串vector</span></span><br><span class="line"><span class="comment">     * @return string字符串vector</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    vector&lt;vector&lt;string&gt;&gt; ans;</span><br><span class="line">    vector&lt;string&gt; res;</span><br><span class="line">    unordered_set&lt;string&gt; dict;</span><br><span class="line"></span><br><span class="line">    <span class="function">vector&lt;string&gt; <span class="title">wordDiv</span><span class="params">(string word, vector&lt;string&gt; &amp;dic)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="keyword">for</span> (string &amp;s: dic) &#123;</span><br><span class="line">            dict.<span class="built_in">insert</span>(s);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">dfs</span>(<span class="number">0</span>, word);</span><br><span class="line">        vector&lt;string&gt; finalAns;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">auto</span> &amp;ss: ans) &#123;</span><br><span class="line">            string tmp;</span><br><span class="line">            <span class="keyword">for</span> (string &amp;s: ss) &#123;</span><br><span class="line">                tmp += s + <span class="string">&quot; &quot;</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            tmp.<span class="built_in">pop_back</span>();</span><br><span class="line">            finalAns.<span class="built_in">push_back</span>(tmp);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> finalAns;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">dfs</span><span class="params">(<span class="type">int</span> idx, <span class="type">const</span> string &amp;s)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (idx &gt;= s.<span class="built_in">length</span>()) &#123;</span><br><span class="line">            <span class="keyword">if</span> (idx == s.<span class="built_in">length</span>()) &#123;</span><br><span class="line">                ans.<span class="built_in">push_back</span>(res);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> cnt = <span class="number">1</span>; (idx + cnt) &lt;= s.<span class="built_in">size</span>(); ++cnt) &#123;</span><br><span class="line">            string w = s.<span class="built_in">substr</span>(idx, cnt);</span><br><span class="line">            <span class="keyword">if</span> (dict.<span class="built_in">find</span>(w) != dict.<span class="built_in">end</span>()) &#123;</span><br><span class="line">                res.<span class="built_in">push_back</span>(w);</span><br><span class="line">                <span class="built_in">dfs</span>(idx + cnt, s);</span><br><span class="line">                res.<span class="built_in">pop_back</span>();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<h2 id="栈"><a href="#栈" class="headerlink" title="栈"></a>栈</h2><h3 id="NC171-直方图内最大矩形"><a href="#NC171-直方图内最大矩形" class="headerlink" title="NC171 直方图内最大矩形"></a><strong>NC171</strong> <strong>直方图内最大矩形</strong></h3><p>单调栈</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param heights int整型vector</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">typedef</span> pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt; P;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">largestRectangleArea</span><span class="params">(vector&lt;<span class="type">int</span>&gt; &amp;heights)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="type">int</span> ans = <span class="number">0</span>;</span><br><span class="line">        stack&lt;P&gt; st;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> h: heights) &#123;</span><br><span class="line">            <span class="keyword">if</span> (st.<span class="built_in">empty</span>() || h &gt;= st.<span class="built_in">top</span>().first) &#123;</span><br><span class="line">                st.<span class="built_in">push</span>(&#123;h, <span class="number">1</span>&#125;);</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="type">int</span> sumWidth = <span class="number">0</span>;</span><br><span class="line">            <span class="keyword">while</span> (!st.<span class="built_in">empty</span>() &amp;&amp; h &lt; st.<span class="built_in">top</span>().first) &#123;</span><br><span class="line">                P p = st.<span class="built_in">top</span>();</span><br><span class="line">                ans = <span class="built_in">max</span>(ans, p.first * (p.second + sumWidth));</span><br><span class="line">                sumWidth += p.second;</span><br><span class="line">                st.<span class="built_in">pop</span>();</span><br><span class="line">            &#125;</span><br><span class="line">            st.<span class="built_in">push</span>(&#123;h, sumWidth + <span class="number">1</span>&#125;);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> sumWidth = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span> (!st.<span class="built_in">empty</span>()) &#123;</span><br><span class="line">            P p = st.<span class="built_in">top</span>();</span><br><span class="line">            ans = <span class="built_in">max</span>(ans, p.first * (p.second + sumWidth));</span><br><span class="line">            sumWidth += p.second;</span><br><span class="line">            st.<span class="built_in">pop</span>();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<h3 id="NC237-最大矩形"><a href="#NC237-最大矩形" class="headerlink" title="NC237 最大矩形"></a><strong>NC237</strong> <strong>最大矩形</strong></h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/5720efc1bdff4ca3a7dad37ca012cb60?tpId=117&tqId=39474&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/5720efc1bdff4ca3a7dad37ca012cb60?tpId=117&amp;tqId=39474&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<p>这个地方可以抽象、转化成上面的<strong>直方图内最大矩形</strong>，很需要想象力和转换能力。整体时间复杂度为O(m*n*n)</p>
<p>使用单调栈，可以优化到O(m*n)。不过这里使用另一种也不错的方式解决。</p>
<p><strong>枚举+前缀和</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param matrix int整型vector&lt;vector&lt;&gt;&gt;</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">maximalRectangle</span><span class="params">(vector&lt;vector&lt;<span class="type">int</span>&gt; &gt; &amp;g)</span> </span>&#123;</span><br><span class="line">        <span class="type">int</span> m = g.<span class="built_in">size</span>();</span><br><span class="line">        <span class="type">int</span> n = g[<span class="number">0</span>].<span class="built_in">size</span>();</span><br><span class="line">        vector&lt;vector&lt;<span class="type">int</span>&gt;&gt; <span class="built_in">ps</span>(m, <span class="built_in">vector</span>&lt;<span class="type">int</span>&gt;(n));</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; m; ++i) &#123;</span><br><span class="line">            vector&lt;<span class="type">int</span>&gt; &amp;p = ps[i];</span><br><span class="line">            vector&lt;<span class="type">int</span>&gt; &amp;a = g[i];</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; n; ++j) &#123;</span><br><span class="line">                p[j] = j ? p[j - <span class="number">1</span>] + a[j] : a[j];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> ans = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> j1 = <span class="number">0</span>; j1 &lt; n; ++j1) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j2 = j1; j2 &lt; n; ++j2) &#123;</span><br><span class="line">                <span class="type">int</span> now = <span class="number">0</span>;</span><br><span class="line">                <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; m; ++i) &#123;</span><br><span class="line">                    <span class="type">int</span> s = ps[i][j2] - (j1 ? ps[i][j1 - <span class="number">1</span>] : <span class="number">0</span>);</span><br><span class="line">                    <span class="type">bool</span> ok = s == j2 - j1 + <span class="number">1</span>;</span><br><span class="line">                    <span class="keyword">if</span> (ok) &#123;</span><br><span class="line">                        ++now;</span><br><span class="line">                        ans = <span class="built_in">max</span>(ans, now * (j2 - j1 + <span class="number">1</span>));</span><br><span class="line">                    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                        now = <span class="number">0</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">                ans = <span class="built_in">max</span>(ans, now * (j2 - j1 + <span class="number">1</span>));</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<blockquote>
<p>题解</p>
<p><a target="_blank" rel="noopener" href="https://song-yang-ji.blog.csdn.net/article/details/107504273">https://song-yang-ji.blog.csdn.net/article/details/107504273</a></p>
</blockquote>
<h3 id="NC240-计算器-一"><a href="#NC240-计算器-一" class="headerlink" title="NC240 计算器(一)"></a><strong>NC240</strong> <strong>计算器(一)</strong></h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/9b1fca7407954ba5a6f217e7c3537fed?tpId=117&tqId=39585&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/9b1fca7407954ba5a6f217e7c3537fed?tpId=117&amp;tqId=39585&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param s string字符串</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    stack&lt;<span class="type">int</span>&gt; nums;</span><br><span class="line">    stack&lt;<span class="type">char</span>&gt; opts;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">handle</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="type">int</span> b = nums.<span class="built_in">top</span>();</span><br><span class="line">        nums.<span class="built_in">pop</span>();</span><br><span class="line">        <span class="type">int</span> a = nums.<span class="built_in">top</span>();</span><br><span class="line">        nums.<span class="built_in">pop</span>();</span><br><span class="line">        <span class="type">char</span> c = opts.<span class="built_in">top</span>();</span><br><span class="line">        opts.<span class="built_in">pop</span>();</span><br><span class="line">        <span class="type">int</span> res;</span><br><span class="line">        <span class="keyword">switch</span> (c) &#123;</span><br><span class="line">            <span class="keyword">case</span> <span class="string">&#x27;+&#x27;</span>:</span><br><span class="line">                res = a + b;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            <span class="keyword">case</span> <span class="string">&#x27;-&#x27;</span>:</span><br><span class="line">                res = a - b;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        nums.<span class="built_in">push</span>(res);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">calculate</span><span class="params">(string s)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (!<span class="built_in">isNumber</span>(s[<span class="number">0</span>])) &#123;</span><br><span class="line">            s = <span class="string">&quot;0&quot;</span> + s;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="type">int</span> i;</span><br><span class="line">        <span class="type">int</span> n = s.<span class="built_in">size</span>();</span><br><span class="line">        <span class="keyword">for</span> (i = <span class="number">0</span>; i &lt; s.<span class="built_in">length</span>();) &#123;</span><br><span class="line">            <span class="keyword">if</span> (<span class="built_in">isNumber</span>(s[i])) &#123;</span><br><span class="line">                <span class="type">int</span> num = <span class="number">0</span>;</span><br><span class="line">                <span class="keyword">while</span> (i &lt; n &amp;&amp; <span class="built_in">isNumber</span>(s[i])) &#123;</span><br><span class="line">                    num = num * <span class="number">10</span> + (s[i++] - <span class="string">&#x27;0&#x27;</span>);</span><br><span class="line">                &#125;</span><br><span class="line">                nums.<span class="built_in">push</span>(num);</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="keyword">if</span> (s[i] == <span class="string">&#x27;(&#x27;</span>) &#123;</span><br><span class="line">                    opts.<span class="built_in">push</span>(s[i]);</span><br><span class="line">                &#125; <span class="keyword">else</span> <span class="keyword">if</span> (s[i] == <span class="string">&#x27;)&#x27;</span>) &#123;</span><br><span class="line">                    <span class="type">char</span> opt;</span><br><span class="line">                    <span class="keyword">while</span> ((opt = opts.<span class="built_in">top</span>()) &amp;&amp; opt != <span class="string">&#x27;(&#x27;</span>) &#123;</span><br><span class="line">                        <span class="built_in">handle</span>();</span><br><span class="line">                    &#125;</span><br><span class="line">                    opts.<span class="built_in">pop</span>();</span><br><span class="line">                &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                    <span class="keyword">while</span> (!(opts.<span class="built_in">empty</span>() || opts.<span class="built_in">top</span>() == <span class="string">&#x27;(&#x27;</span>)) &#123;</span><br><span class="line">                        <span class="built_in">handle</span>();</span><br><span class="line">                    &#125;</span><br><span class="line">                    opts.<span class="built_in">push</span>(s[i]);</span><br><span class="line">                &#125;</span><br><span class="line">                ++i;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span> (!opts.<span class="built_in">empty</span>()) &#123;</span><br><span class="line">            <span class="built_in">handle</span>();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> nums.<span class="built_in">top</span>();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">isNumber</span><span class="params">(<span class="type">char</span> c)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="string">&#x27;0&#x27;</span> &lt;= c &amp;&amp; c &lt;= <span class="string">&#x27;9&#x27;</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<h2 id="其他"><a href="#其他" class="headerlink" title="其他"></a>其他</h2><p>NC130 分糖果问题</p>
<p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/76039109dd0b47e994c08d8319faa352?tpId=117&tqId=37806&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/76039109dd0b47e994c08d8319faa352?tpId=117&amp;tqId=37806&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<p>solution: 对于某个位置，计算从前&#x2F;后遍历，递增的位次，即连续递增的次数。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * pick candy</span></span><br><span class="line"><span class="comment">     * @param arr int整型vector the array</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">candy</span><span class="params">(vector&lt;<span class="type">int</span>&gt; &amp;a)</span> </span>&#123;</span><br><span class="line">        <span class="type">int</span> n = a.<span class="built_in">size</span>();</span><br><span class="line">        a.<span class="built_in">insert</span>(a.<span class="built_in">begin</span>(), inf);</span><br><span class="line">        a.<span class="built_in">push_back</span>(inf);</span><br><span class="line">        <span class="function">vector&lt;<span class="type">int</span>&gt; <span class="title">f1</span><span class="params">(n + <span class="number">10</span>)</span></span>;</span><br><span class="line">        <span class="function">vector&lt;<span class="type">int</span>&gt; <span class="title">f2</span><span class="params">(n + <span class="number">10</span>)</span></span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; ++i) &#123;</span><br><span class="line">            <span class="keyword">if</span>(a[i] &gt; a[i - <span class="number">1</span>]) &#123;</span><br><span class="line">                f1[i] = f1[i - <span class="number">1</span>] + <span class="number">1</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                f1[i] = <span class="number">0</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = n; i &gt;= <span class="number">1</span>; --i) &#123;</span><br><span class="line">            <span class="keyword">if</span>(a[i] &gt; a[i + <span class="number">1</span>]) &#123;</span><br><span class="line">                f2[i] = f2[i + <span class="number">1</span>] + <span class="number">1</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                f2[i] = <span class="number">0</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> ans = n;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">            ans += <span class="built_in">max</span>(f1[i], f2[i]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>






    </div>

    
    
    

    <footer class="post-footer">

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/2022/06/27/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91%E3%80%81%E5%93%88%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81/" rel="prev" title="哈夫曼树、哈夫曼编码">
                  <i class="fa fa-chevron-left"></i> 哈夫曼树、哈夫曼编码
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/2022/07/26/JUnit%E5%92%8CMockito/" rel="next" title="JUnit和Mockito">
                  JUnit和Mockito <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>






</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 
  <span itemprop="copyrightYear">2023</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">SongyangJi</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/muse/" rel="noopener" target="_blank">NexT.Muse</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>
  <div class="sidebar-dimmer"></div>
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up fa-lg"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


  
  <script src="https://cdnjs.cloudflare.com/ajax/libs/animejs/3.2.1/anime.min.js" integrity="sha256-XL2inqUJaslATFnHdJOi9GfQ60on8Wx1C2H8DYiN1xY=" crossorigin="anonymous"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/schemes/muse.js"></script><script src="/js/next-boot.js"></script>

  <script src="https://cdnjs.cloudflare.com/ajax/libs/hexo-generator-searchdb/1.4.1/search.js" integrity="sha256-1kfA5uHPf65M5cphT2dvymhkuyHPQp5A53EGZOnOLmc=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>





  





</body>
</html>
